\section{运算及关系　习题答案}

    \subsubsection{习题}

    \begin{exercise}
        \begin{enumerate}
            \item $f_1:(a,b)\mapsto a$
            \item $f_2:(a,b)\mapsto 1$
            \item 不可能，因为$|A \times A| > |A|$。
        \end{enumerate}
    \end{exercise}

    \begin{exercise}
        $f_1:(a,b)\mapsto a$，
        $f_2:(a,b)\mapsto b$
    \end{exercise}

    \begin{exercise}
        设$K = \{n \in \mathbb{N}^+ \mid n > 1 \}$，任何的$C \ne D$，
        而$K \subseteq C,D$ 都满足条件。
    \end{exercise}

    \begin{exercise}
        \begin{enumerate}
            \item 不是，其不具备传递性；
            \item 是；
            \item 不是，其不具备反身性、传递性；
            \item 是。
        \end{enumerate}
    \end{exercise}

    \begin{exercise}
        \begin{enumerate}
            \item 满足交换律，不满足结合律；
            \item 满足交换律和结合律；
            \item 满足交换律，不满足结合律；
            \item 不满足交换律和结合律。
        \end{enumerate}
    \end{exercise}

    \begin{exercise}
        \begin{enumerate}
            \item 反身性：任取$a \in \mathbb{Z}$，$(a-a)=0$，$3 \mid 0$，所以$aRa$；
                    对称性：任取$a,b \in \mathbb{Z}$，$aRb \Rightarrow 3 \mid (a-b) \Rightarrow 3 \mid (b-a) \Rightarrow bRa$；
                    传递性：任取$a,b,c \in \mathbb{Z}$，$aRb, bRc \Rightarrow 3 \mid (a-b), 3 \mid (b-c) \Rightarrow a-b=3m, b-c = 3n(m,n \in \mathbb{Z}) \Rightarrow a - c = (a - b) + (b - c) = 3(m+n) \Rightarrow aRc$；
                    因此$R$ 是等价关系。$\bar{0},\bar{1},\bar{2}$分别指所有被三整除的数构成的集合，除以三余一的数构成的集合，除以三余二的数构成的集合。
            \item 略；
            \item 我们任取$m_1,m_2,n_1,n_2 \in \mathbb{Z}$，$r_1,r_2 \in \{0,1,2\}$，
                    显然$(3m_i + r_i) R (3n_i + r_i)$（$i = 1,2$），以及$3m_i+r_i$ 可以取到任意整数。
                    接下来，我们有
                    \begin{align}
                        & (3m_1+r_1)(3m_2+r_2) - (3n_1+r_1)(3n_2+r_2)               \nonumber  \\ 
                     =\ & 9m_1m_2+3m_2r_1+3m_1r_2 -9n_1n_2 -3r_1n_2 - 3r_2n_1       \nonumber 
                    \end{align}
                    这个式子显然被$3$整除，因此$(3m_1+r_1)(3m_2+r_2) R (3n_1+r_1)(3n_2+r_2)$，
                    所以$R$对乘法是一个同余关系。乘法表略。
        \end{enumerate}
    \end{exercise}

    \subsubsection{补充题}

    \begin{exercise}
        $(f\times g)(a,b)=(f(a), g(b))$，而$f(a)\in C, g(b) \in D$，
        所以$(f(a), g(b)) \in C\times D$，进而说明$f\times g:A\times B \rightarrow C \times D$。
    \end{exercise}

    \begin{exercise}
        不正确。在证明过程中，证明者默认了任取$a \in A$，总存在一个$b \in A$ 使得 $a R b$，
        但这个前提无法被保证；因此，对于没有任何其他元素与之有关系$R$的元素，其无法推出反身性。
    \end{exercise}

    \begin{exercise}
        \begin{enumerate}
            \item {
                我们直接判断$R_1$是否是等价关系：
                首先，$\forall a \in A$，因为$a=a$所以$aR_1a$，反身性成立；
                接下来，当$a R_1 b$时，如果$a=b$，则$b R_1 a$显然成立，
                如果$aRb$的话，按定义$b R_1 a$，第三种情况的证明和第二种情况类似，传递性成立；
                最后，设$a R_1 b, b R_1 c$，如果$a=b=c$，则显然$a R_1 c$，
                如果$a R b$（或$b R a$），$b=c$，亦显然$a R_1 c$，
                如果$a R b$（或$b R a$），$b R c$（或$c R b$），这无法推出$a R c$或者$cRa$，因此传递性不成立。
                综上，$R_1$ 不是等价关系。
            }
            \item {
                任取$a \in A$，取$x_1 = x_2 = \cdots =x_{n-1} = a$，则$a R_2 a$成立，反身性成立；
                设$a R_2 b$，其中$a R_1 x_1, x_1 R_1 x_2, \cdots, x_{n-1} R_1 b$，因为$R_1$满足对称性，
                因此取$y_i = x_{n-i}$（$i = 1,2,\cdots,n-1$），则有$b R_1 y_1, y_1 R_1 y_2,\cdots,y_{n-1} R_1 a$，
                进而$b R_2 a$，对称性成立；
                设$a R_2 b$，$b R_2 c$，其中$a R_1 x_1, x_1 R_1 x_2, \cdots, x_{n-1} R_1 b$，$b R_1 y_1, y_1 R_1 y_2, \cdots, y_{m-1} R_1 c$，
                取$z_i = x_i$（$i= 1,2,\cdots,n-1$），$z_n = b$，$z_{n+i} = y_i$（$i = 1,2,\cdots,m-1$），则$a R_2 c$，传递性成立。
                所以$R_2$是等价关系。
            }
            \item {
                若$R$ 是等价关系，则$R_1$ 是等价关系。
                当$xR_2y$时，按定义，$xR_1y$，进而$x=y$或$xRy$，这都说明$xRy$；
                如果$xRy$，则显然$xR_1y$，进而$xR_2y$。
            }
            \item {
                $R_1: aR_1b \Leftrightarrow |a-b|\in\{0,m\}$ ， $R_2: aR_2b \Leftrightarrow a \equiv b (\text{mod } m)$
            }
        \end{enumerate}
    \end{exercise}

    \begin{exercise}
        充分性证明：
        因为$\bar{a} = \bar{c}$，$\bar{b} = \bar{d}$，
        所以$aRc$，$bRd$，
        又因为$R$ 是对于 $\circ$ 的同余关系，
        所以$(a\circ b) R (c\circ d)$，
        进而$\overline{(a\circ b)} = \overline{(c\circ d)}$。

        必要性证明：
        $\bar{a}=\bar{c}, \bar{b} = \bar{d} \Rightarrow \overline{(a\circ b)} = \overline{(c\circ d)}$
        充分条件和必要条件分别等价于$aRc, bRd$，$(a\circ b) R (c\circ d)$，
        进而$aRc, bRd \Rightarrow (a\circ b) R (c\circ d)$，
        这直接说明了$R$ 是对于 $\circ$ 的同余关系。
    \end{exercise}
